package leetcode.median;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * ClassName: $17_LetterCombinations
 * Description:
 * date: 2022-01-10 21:37
 *
 * @author liyifan
 */
public class $17_LetterCombinations {
    public List<String> letterCombinations(String digits) {
        List<String> res = new LinkedList<>();
        if (digits.length() == 0)
            return res;
        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        bp(res, map, digits,0, new StringBuffer());
        return res;
    }

    public void bp(List<String> res, Map<Character, String> map, String digits, int index, StringBuffer sb){
        if (index == digits.length()) {
            res.add(sb.toString());
        } else {
            String words = map.get(digits.charAt(index));
            for (int i = 0;i < words.length(); i++) {
                sb.append(words.charAt(i));
                bp(res, map, digits, index + 1, sb);
                sb.deleteCharAt(index);
            }
        }
    }
}
